# 作者: YYJ
# 2025年06月14日19时13分14秒
# 2486249622@qq.com

# 排序算法共同点：外层控制有序或无序列表个数，内层找到元素位置

import random


class Sort:
    def __init__(self, arr_num, num_range):
        self.arr = []
        self.arr_num = arr_num  # 数组长度
        self.num_range = num_range  # 数字范围
        self.__create_random_num()

    def __create_random_num(self):
        """
        实现随机数
        :return:
        """
        for i in range(self.arr_num):
            self.arr.append(random.randint(0, self.num_range - 1))  # randint左闭右闭

    def bubble_sort(self):
        for i in range(self.arr_num, 1, -1):
            flag = False  # 判断是否交换过, 如果没有交换过则结束循环
            for j in range(i - 1):
                if self.arr[j] > self.arr[j + 1]:
                    self.arr[j], self.arr[j + 1] = self.arr[j + 1], self.arr[j]
                    flag = True
                if flag is False:
                    break

    def select_sort(self):
        for i in range(0, self.arr_num - 1):
            min_pos = i
            for j in range(i + 1, self.arr_num):
                if self.arr[j] < self.arr[min_pos]:
                    min_pos = j  # 记录最小值的位置
            self.arr[min_pos], self.arr[i] = self.arr[i], self.arr[min_pos]

    def insert_sort(self):
        for i in range(1, self.arr_num):
            insert_val = self.arr[i]
            j = i - 1
            while j >= 0:  # 若使用for循环，无法在找到找到插入位置退出循环后将元素插入到该位置(即j丢失)
                if self.arr[j] > insert_val:
                    self.arr[j + 1] = self.arr[j]
                    j -= 1
                else:
                    break
            self.arr[j + 1] = insert_val

    def shell_sort(self):
        gap = self.arr_num >> 1
        while gap > 0:
            for i in range(gap, self.arr_num):
                insert_val = self.arr[i]
                j = i - gap
                while j >= 0:  # 若使用for循环，无法在找到找到插入位置退出循环后将元素插入到该位置(即j丢失)
                    if self.arr[j] > insert_val:
                        self.arr[j + gap] = self.arr[j]
                        j -= gap
                    else:
                        break
                self.arr[j + gap] = insert_val
            gap = gap >> 1

    def __partition__(self, left, right):
        """
        以right为枢轴元素，一次划分确定枢轴元素的位置
        :param left: 左边界
        :param right: 右边界
        :return: 枢轴元素的位置
        """
        k = left    # 标记小于 pivot 的区域边界
        # 随机选取pivot，再和right交换位置
        self.arr[right], self.arr[left + random.randint(0, right - left)] = (
            self.arr[left + random.randint(0, right - left)], self.arr[right])
        for i in range(left, right):
            if self.arr[i] < self.arr[right]:  # 如果当前元素小于 pivot 值
                self.arr[i], self.arr[k] = self.arr[k], self.arr[i]  # 交换位置
                k += 1  # 标记小于 pivot 的区域边界
        self.arr[k], self.arr[right] = self.arr[right], self.arr[k]  # 将 pivot 放到正确的位置
        return k  # 返回 pivot 的最终位置

    def quick_sort(self, left, right):
        if left < right:
            pivot = self.__partition__(left, right)
            self.quick_sort(left, pivot - 1)
            self.quick_sort(pivot + 1, right)


if __name__ == '__main__':
    s = Sort(10, 100)
    print(s.arr)
    # s.bubble_sort()
    # print(s.arr)
    # s.select_sort()
    # print(s.arr)
    # s.insert_sort()
    # print(s.arr)
    # s.shell_sort()
    # print(s.arr)
    s.quick_sort(0, s.arr_num - 1)
    print(s.arr)
